import java.awt.*;
import java.awt.event.*;

//dfs是整体对着一个方向一直走，没有岔路，但斗折蛇行
//bfs是层层尽可能分叉，但各个岔路不够弯曲不够复杂
public class AlgoVisualizer {

    private static int DELAY = 20;
    private static int blockSide = 8;

    private MazeData data;
    private AlgoFrame frame;
    private static final int d[][] = {{-1,0},{0,1},{1,0},{0,-1}};

    public AlgoVisualizer(int N, int M){

        // 初始化数据
        data = new MazeData(N, M);
        int sceneHeight = data.N() * blockSide;
        int sceneWidth = data.M() * blockSide;

        // 初始化视图
        EventQueue.invokeLater(() -> {
            frame = new AlgoFrame("Random Maze Generation Visualization", sceneWidth, sceneHeight);
            frame.addKeyListener(new AlgoKeyListener());

            new Thread(() -> {
                run();
            }).start();
        });
    }

    private void run(){

        setRoadData(-1, -1);

        RandomQueue<Position> queue = new RandomQueue<Position>();
        /*
         * 事实上 这儿的随机队列用随机索引结果并不够随机 而随机使用栈和队列随机性最好 是因为随机索引的话深度和广度的随机性是不稳定的，受到上一次选择结果的影响
         * 同端进出就是栈 1/2； 异端就是队列 1/2；
         */
        Position first = new Position(data.getEntranceX(), data.getEntranceY()+1);
        queue.add(first);
        data.visited[first.getX()][first.getY()] = true;
        data.openMist(first.getX(), first.getY());

        while(queue.size() != 0){
            Position curPos = queue.remove();
            
//			ArrayList<int[]> nexts = new ArrayList<>();
//			for (int i = 0; i < 4; i++) {
//				int newX = curPos.getX() + d[i][0] * 2; // 间隔分布的顶点来生成树
//				int newY = curPos.getY() + d[i][1] * 2;
//				if (data.inArea(newX, newY))
//					nexts.add(new int[] { newX, newY, i });
//			}
//
//			int flag = 0;// 第几次判断成功
//			for (int[] next : nexts) {
//				if (!data.visited[next[0]][next[1]]) {
//					flag++;// 第几次进来
//					if (flag == 1)
//						queue.addInside(new Position(next[0], next[1]));
//					else
//						queue.add(new Position(next[0], next[1]));
//
//					data.visited[next[0]][next[1]] = true;
//					data.openMist(next[0], next[1]);
//					// 重新绘制 打通顶点之间的墙体 重新绘制的时候是把所有data都重新绘制一遍 使得对data的修改都生效
//					setRoadData(curPos.getX() + d[next[2]][0], curPos.getY() + d[next[2]][1]);
//				}
//			}
			
          //V2
//            ArrayList<int[]> nexts = new ArrayList<>();
//            for (int i = 0; i < 4; i++) {
//                int newX = curPos.getX() + d[i][0]*2; //间隔分布的顶点来生成树
//                int newY = curPos.getY() + d[i][1]*2;
//                if(data.inArea(newX, newY))
//                	nexts.add(new int[]{newX, newY, i});
//			}
//            
//            if(nexts.size() != 4) {
//            	for (int[] next : nexts) {
//            		if (!data.visited[next[0]][next[1]]) {
//            			queue.add(new Position(next[0], next[1]));
//            			data.visited[next[0]][next[1]] = true;
//            			data.openMist(next[0], next[1]);
//            			// 重新绘制 打通顶点之间的墙体 重新绘制的时候是把所有data都重新绘制一遍 使得对data的修改都生效
//            			setRoadData(curPos.getX() + d[next[2]][0], curPos.getY() + d[next[2]][1]);
//            		}
//            	}
//            }
//            else {
//            	int flag = 0;//第几次判断成功
//            	for (int i = 0; i < 4; i++) {
//					int[] next = nexts.get(i);
//					if (!data.visited[next[0]][next[1]]) {
//						flag ++;//第几次进来
//						if (flag == 1)
//							queue.addInside(new Position(next[0], next[1]));
//						else
//							queue.add(new Position(next[0], next[1]));
//
//						data.visited[next[0]][next[1]] = true;
//						data.openMist(next[0], next[1]);
//						// 重新绘制 打通顶点之间的墙体 重新绘制的时候是把所有data都重新绘制一遍 使得对data的修改都生效
//						setRoadData(curPos.getX() + d[next[2]][0], curPos.getY() + d[next[2]][1]);
//					}
//				}
//			}

          //V1
            for(int i = 0 ; i < 4  ; i ++){
                int newX = curPos.getX() + d[i][0]*2; //间隔分布的顶点来生成树
                int newY = curPos.getY() + d[i][1]*2;

                if(data.inArea(newX, newY) && !data.visited[newX][newY]){
                    queue.add(new Position(newX, newY));
                    data.visited[newX][newY] = true;
                    data.openMist(newX, newY);
                    //重新绘制    打通顶点之间的墙体   重新绘制的时候是把所有data都重新绘制一遍  使得对data的修改都生效
                    setRoadData(curPos.getX() + d[i][0], curPos.getY() + d[i][1]);
                }
            }
        }

        setRoadData(-1, -1); //无效参数用来刷新 并不打通某位置的墙体
    }

    private void setRoadData(int x, int y){
        if(data.inArea(x, y))
            data.maze[x][y] = MazeData.ROAD;

        frame.render(data);
        AlgoVisHelper.pause(DELAY);
    }

    private boolean go(int x, int y){

        if(!data.inArea(x,y))
            throw new IllegalArgumentException("x,y are out of index in go function!");

        data.visited[x][y] = true;
        setPathData(x, y, true);

        if(x == data.getExitX() && y == data.getExitY())
            return true;

        for(int i = 0 ; i < 4 ; i ++){
            int newX = x + d[i][0];
            int newY = y + d[i][1];
            if(data.inArea(newX, newY)
            		&& data.maze[newX][newY] == MazeData.ROAD 
                    && !data.visited[newX][newY])
                if(go(newX, newY))
                    return true;
        }

        // 回溯
        setPathData(x, y, false);

        return false;
    }

    private void setPathData(int x, int y, boolean isPath){
        if(data.inArea(x, y))
            data.path[x][y] = isPath;

        frame.render(data);
        AlgoVisHelper.pause(DELAY);
    }

    private class AlgoKeyListener extends KeyAdapter{

        @Override
        public void keyReleased(KeyEvent event){
            if(event.getKeyChar() == ' '){
                for(int i = 0 ; i < data.N() ; i ++)
                    for(int j = 0 ; j < data.M() ; j ++)
                        data.visited[i][j] = false;

                new Thread(() -> {
                    go(data.getEntranceX(), data.getEntranceY());
                }).start();
            }
        }
    }

    public static void main(String[] args) {

        int N = 101;
        int M = 101;

        AlgoVisualizer vis = new AlgoVisualizer(N, M);

    }
}